package com.leetcode.problems_03;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 回溯算法
 *
 *
 * @Author: WuPeng
 * @Date: 2021/5/17 2:33 下午
 */
public class PhoneNumberCombination {

    public static List<String> res = new ArrayList<>();

    public static StringBuilder tmpStr = new StringBuilder();

    public static List<String> solution(String digits){

        String[] chars = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        backTracking(digits, chars, 0);

        return res;
    }

    public static void backTracking(String digits, String[] chars, int num){
        // 完成一次遍历便将结果添加到结果集中
        if (num == digits.length()){
            res.add(tmpStr.toString());
            return;
        }

        //当前数字对应的字母
        String str = chars[digits.charAt(num) - '0'];

        for (int i = 0; i < str.length(); i++) {
            tmpStr.append(str.charAt(i));
            backTracking(digits, chars, num+1);
            // 删除最后一个字符，然后继续下一次循环
            tmpStr.deleteCharAt(tmpStr.length()-1);
        }

    }

    public static void main(String[] args) {
        solution("23");
        System.out.println(Arrays.toString(res.toArray()));
    }
}
